6장. 빠른 그릇과 책갈피 (자료구조·복잡도)

출처: 『AI 엔지니어링 선수지식』(youtubedu 자체 제작 학습노트) | 입문판 재구성 — 노트가 1차 소스(PDF 원본 없음)

코드는 분위기만 — Python 한 줄 한 줄을 다 몰라도 됩니다. 표의 '비유'와 '위험'만 봐도 충분해요.

이 장은 0장 용어집과 척추를 한 번 더 풀어 쓴 곳이다.

막히는 말이 나오면 0장으로 돌아가면 된다. 0장에 없는 새 말은 아래 "0. 이 장의 새 단어"에 다 적어 둔다.

들어가며 — 이런 적 있죠?

긴 글을 AI 에게 붙여 넣었더니 답이 느리게 나온 적 있죠?

짧은 질문은 즉시 답하는데, 긴 문서를 넣으면 한참 끙끙댄다.

"글이 두 배 길어졌을 뿐인데, 왜 네 배쯤 느려지지?"

또 이런 적도 있다. 같은 대화를 길게 이어 가면, 뒤로 갈수록 한 마디 한 마디가 점점 더 느려진다.

이 두 장면에는 공통점이 있다.

데이터가 늘어날 때, 일하는 시간이 그보다 훨씬 빨리 늘어난다.

데이터가 두 배인데 시간은 네 배가 되는 이런 현상을 다루는 게 이 장이다.

그리고 이 폭증을 어떻게 그릇(자료구조)과 책갈피(캐시)로 누그러뜨리는지를 본다.

말로만 들으면 와닿지 않으니, 방금 그 장면을 코드로 한번 보자.

# 100명에게 한 명씩 전화 = 100번 / 모두가 모두와 1:1 만남 = 약 10,000번
# 사람 수가 100배가 아니라, 일하는 횟수가 100배로 늘어난다
people = 100
one_by_one = people          # 100 (한 명씩)
everyone_meets = people * people   # 10,000 (모두끼리)

사람은 100명인데 일은 10,000번이다.

이렇게 "데이터가 늘 때 일이 얼마나 빨리 불어나는가"를 재는 것이 이 장의 첫 주제다.

이 장에서 우리는 그 늘어나는 속도를 어떻게 읽고, 어떻게 그릇과 책갈피로 줄이는지만 본다.

0. 이 장의 새 단어

0장 용어집에 없던 말만 여기 모아 둔다.

각 단어는 [한 문장 뜻 + 일상비유 + 한 줄 예] 3종으로 적었다.

본문에서 막히면 이 박스로 돌아오면 된다.

Big-O 표기 (빅오)

한 문장 뜻 — 데이터가 N개로 늘 때, 일하는 시간이 얼마나 빨리 늘어나는지를 적는 표기.

일상비유 — 인원이 늘 때 모임 준비가 얼마나 힘들어지는지의 등급표. 단톡방 공지는 인원이 늘어도 한 번, 한 명씩 전화는 인원만큼, 모두끼리 1:1 만남은 인원의 제곱만큼 힘들어진다.

한 줄 예 —

# N이 100일 때 — O(N)은 100번, O(N²)은 10,000번 (100배 차이)
N = 100
linear = N           # O(N) = 100
quadratic = N * N    # O(N²) = 10,000

해시테이블 (hash table)

한 문장 뜻 — 번호(열쇠)만 알면 통째로 뒤지지 않고 곧장 값을 꺼내는 그릇.

일상비유 — 번호 달린 사물함. 통로를 다 뒤지지 않고, 번호만 알면 그 칸을 즉시 연다.

한 줄 예 —

# "영희"라는 열쇠로 전화번호를 곧장 꺼냄 (다 뒤지지 않음)
phone = {"철수": "010-1", "영희": "010-2"}
print(phone["영희"])   # 즉시

KV 캐시 (KV cache)

한 문장 뜻 — 이미 계산해 둔 결과를 보관했다가, 다음에 같은 계산이 필요하면 다시 안 하고 꺼내 쓰는 저장고.

일상비유 — 책갈피. 읽던 페이지를 매번 처음부터 다시 펴지 않고, 책갈피를 꽂아 둔 데서 바로 이어 읽는다.

한 줄 예 —

# 한 번 계산한 값을 저장 → 다음엔 다시 계산 안 하고 꺼냄
cache = {}
cache[5] = "이미 계산한 결과"   # 보관
print(cache[5])                 # 재계산 없이 즉시 꺼냄

이 장에서 딱 3가지만

TL;DR 3박스

박스 1 — 일이 늘어나는 속도부터 읽어라 (Big-O)

데이터가 N개일 때 일이 N번 느는지, N의 제곱번 느는지가 속도를 가른다.

AI 가 긴 글에서 느려지는 건, 모든 단어가 모든 단어를 봐서 일이 N의 제곱으로 불어나기 때문이다.

박스 2 — 그릇을 잘 고르면 즉시 찾는다 (해시)

통째로 뒤지면 N번이지만, 번호 달린 사물함(해시테이블)에 넣어 두면 번호 하나로 즉시 꺼낸다.

AI 의 토크나이저(단어↔숫자 사전)가 바로 이 사물함이다.

박스 3 — 한 번 한 계산은 책갈피로 아껴라 (KV 캐시)

매번 처음부터 다시 계산하면 N의 제곱이지만, 계산해 둔 걸 보관(캐시)하면 새것만 계산하면 된다.

긴 대화에서 AI 가 안 멈추는 건 이 책갈피 덕분이다.

학습 목표

이 장을 끝내면 다음을 할 수 있다.

• 데이터가 늘 때 일이 얼마나 빨리 불어나는지(Big-O)를 설명한다.

• O(1)·O(N)·O(N²) 가 어떻게 다른지를 구분한다.

• 해시테이블·큐·KV 캐시가 각각 무엇을 빠르게 해 주는지를 구분한다.

속도를 재설계하거나 어느 그릇이 더 나은지 판단하는 일은 이 장에서 하지 않는다. 지금은 "무엇인지" 알면 된다.

1. Big-O — 일이 얼마나 빨리 불어나나

망가지는 장면

짧은 입력은 즉시 답하던 AI 가, 긴 글을 넣자 한참 멈춘 적 있죠?

# 글이 길어질수록 일이 얼마나 느는지 비교
short = 10
long  = 20            # 글 길이는 2배

# 일이 N의 제곱으로 는다면
print(short * short)   # 100
print(long  * long)    # 400  ← 길이는 2배인데 일은 4배

길이는 2배인데 일은 4배가 됐다.

이렇게 "데이터가 늘 때 일이 얼마나 빨리 느는가"를 한눈에 적는 게 Big-O 표기다.

비유 먼저 — 친구 만나기 세 가지 방법

100명에게 소식을 전한다고 해 보자.

방법 ①은 단톡방 공지. 인원이 100명이든 1,000명이든 한 번이면 끝난다. 이게 O(1)이다.

방법 ②는 한 명씩 전화. 100명이면 100통, 1,000명이면 1,000통. 인원만큼 는다. 이게 O(N)이다.

방법 ③은 모두가 모두와 1:1 만남. 100명이면 약 10,000번이다. 인원의 제곱만큼 는다. 이게 O(N²)이다.

같은 100명인데, 방법에 따라 한 번부터 만 번까지 갈린다.

같은 일도 그릇을 바꾸면 빨라진다

같은 "찾기"라도 어디에 담느냐로 속도가 갈린다.

리스트에서 in 으로 찾으면 앞에서부터 하나씩 본다 — O(N)이다.

집합(set)에 담아 두면 번호로 곧장 꺼낸다 — O(1)이다.

# 리스트에서 찾기 — 앞에서부터 하나씩 (O(N))
nums = list(range(1000000))
print(500000 in nums)   # 끝까지 뒤질 수도 있어 느림

# 집합에서 찾기 — 번호로 곧장 (O(1))
s = set(range(1000000))
print(500000 in s)      # 거의 즉시

같은 100만 개에서 같은 값을 찾는데, 그릇만 바꿔도 속도가 달라진다.

한 문장 정의

Big-O 는 데이터가 N개로 늘 때 일하는 시간이 얼마나 빨리 늘어나는지를 적는 표기이며, O(1) < O(log N) < O(N) < O(N²) 순으로 점점 빨리 불어난다.

진짜 질문은 "지금 빠르냐"가 아니다.

"데이터가 100배 늘면 이 코드가 얼마나 더 느려지느냐"다.

O(N)은 100배만 느려지지만, O(N²)은 10,000배 느려진다.

LLM 연결 — 어텐션은 O(N²)다

AI 의 어텐션은 모든 단어가 모든 단어와 내적(0장 용어)을 한다.

단어 100개면 100×100, 즉 약 10,000번이다.

그래서 글이 2배 길어지면 일은 4배가 된다. 긴 글에서 AI 가 느려지는 진짜 이유다.

더 깊이 — Khan Academy Algorithms

이럴 때 이렇게 — 미니 시나리오

동료가 "이 검색이 너무 느려요" 한다.

코드를 보니 리스트에서 in 으로 100만 개를 매번 뒤지고 있다 — O(N).

답은 "컴퓨터를 더 좋은 걸로 바꾸자"가 아니라 "그릇을 바꾸자"이다.

리스트를 집합(set)으로만 바꿔도 O(1)이 되어 즉시 빨라진다.

2. 해시테이블 — 번호 달린 사물함

망가지는 장면

단어가 백만 개인 사전에서 "강아지"를 찾는데, 처음부터 한 장씩 넘기면 끝이 없다.

# 리스트를 처음부터 한 칸씩 — 운 나쁘면 끝까지 (O(N))
words = ["가방", "강물", "...", "강아지"]
print("강아지" in words)   # 앞에서부터 하나씩 비교

이 "한 칸씩 뒤지기"가 느림의 원인이다.

번호만 알면 곧장 그 칸을 여는 그릇이 있으면 좋겠다. 그게 해시테이블이다.

비유 먼저 — 번호 달린 사물함

지하철 물품보관함을 떠올려 보자.

내 짐이 어디 있는지 통로를 다 뒤지지 않는다.

번호(예: 207번)만 알면 그 칸으로 곧장 가서 즉시 연다.

해시테이블도 똑같다. 열쇠(번호)를 넣으면 어느 칸인지 바로 계산해서, 통째로 뒤지지 않고 즉시 꺼낸다.

# 열쇠 "영희"로 곧장 꺼냄 — 다 뒤지지 않는다 (O(1))
phone = {"철수": "010-1", "영희": "010-2"}
print(phone["영희"])   # 즉시

같이 보면 좋은 그릇 — 트리와 큐

해시테이블 말고도, 자주 쓰는 그릇이 둘 더 있다.

하나는 트리 — 토너먼트 대진표처럼 단계로 좁혀 가며 찾는다. 100명을 단 7단계로 좁히는 O(log N)이다.

다른 하나는 큐 — 줄 서기처럼 먼저 온 게 먼저 나간다(FIFO). 순서를 관리하는 그릇이다.

# 해시(딕셔너리)로 단어 세기 — 한 줄로 즉시 집계
text = ["고양이", "개", "고양이", "고양이", "개"]
count = {}
for w in text:
    count[w] = count.get(w, 0) + 1   # 열쇠로 곧장 더함
print(count)   # {'고양이': 3, '개': 2}

해시는 "곧장 찾기", 트리는 "단계로 좁히기", 큐는 "순서 지키기"다.

한 문장 정의

해시테이블은 열쇠로 어느 칸인지 곧장 계산해, 통째로 뒤지지 않고 O(1)로 값을 꺼내는 그릇이다.

진짜 핵심은 "빠르다"가 아니라 왜 빠른가다.

찾을 칸을 계산해서 바로 가기 때문에, 데이터가 100만 개여도 꺼내는 데 걸리는 시간이 거의 그대로다.

LLM 연결 — 토크나이저가 해시테이블이다

AI 는 단어를 숫자 ID 로 바꿔 다룬다("강아지" → 5821 같은 번호).

이 단어↔ID 사전이 바로 해시테이블이다.

수만 개 단어 중 하나를 찾을 때도, 통째로 뒤지지 않고 번호로 곧장 꺼낸다.

더 깊이 — Khan Academy CS

이럴 때 이렇게 — 미니 시나리오

로그 파일에서 같은 단어가 몇 번 나왔는지 세야 한다.

리스트에 단어를 다 넣고 매번 count() 로 세면, 단어마다 통째로 뒤져 O(N²)이 된다.

답은 딕셔너리(해시) 하나에 count[w] = count.get(w, 0) + 1 로 더하는 것이다.

한 번 훑으며 곧장 집계해 O(N)으로 끝난다.

3. KV 캐시 — 읽던 데를 책갈피로 아끼기

망가지는 장면

대화를 길게 이어 갈수록 AI 가 점점 느려진 적 있죠?

# 캐시 없이 단어 100개를 만들면 — 매번 앞을 다시 다 계산
# 1 + 2 + 3 + ... + 100 = 5050번 (O(N²))
total = 0
for i in range(1, 101):
    total = total + i      # i번째 단어를 만들 때 앞 i개를 다시 봄
print(total)   # 5050

새 단어 하나를 만들 때마다 앞 단어를 처음부터 전부 다시 본다.

이미 한 계산을 또 하는 이 낭비를, 보관해 뒀다 꺼내 쓰면 없앨 수 있다. 그게 KV 캐시다.

비유 먼저 — 책갈피

두꺼운 책을 읽는다고 해 보자.

읽던 데를 표시 안 하면, 다시 펼 때마다 1페이지부터 넘겨 와야 한다.

책갈피를 꽂아 두면, 그 자리부터 바로 이어 읽는다.

KV 캐시도 똑같다. 이미 계산한 단어들의 결과를 보관해 두고, 새 단어만 계산한다.

# 계산한 값을 보관 → 다음엔 다시 계산 안 하고 꺼냄
cache = {}
def fib(n):
    if n < 2:
        return n
    if n in cache:          # 책갈피가 있으면
        return cache[n]     # 다시 계산 안 하고 꺼냄
    cache[n] = fib(n-1) + fib(n-2)
    return cache[n]
print(fib(50))   # 캐시 없으면 수십 초, 있으면 즉시

같은 일을 5050번에서 100번으로

캐시가 있고 없고가 얼마나 큰 차이인지 숫자로 보자.

캐시 없이 단어 100개를 만들면 1+2+...+100 = 5050번이다(O(N²)).

KV 캐시로 앞 99개를 재사용하면, 매번 새것 1번씩 100번이다(O(N)).

# 캐시 없음 — 매번 앞을 다시 (O(N²))
no_cache = sum(range(1, 101))      # 5050

# 캐시 있음 — 새것만 (O(N))
with_cache = 100                   # 100
print(no_cache, with_cache)        # 5050 100

같은 결과를 내는데 일은 50배 차이다.

한 문장 정의

KV 캐시는 이미 계산한 결과를 보관해 두고 새것만 계산하게 해, 어텐션의 O(N²) 반복을 O(N)에 가깝게 줄이는 저장 기법이다.

진짜 핵심은 "저장한다"가 아니다.

같은 계산을 두 번 안 한다는 것이다. 그래서 긴 대화도 매번 새 한 마디만큼만 더 계산하면 된다.

LLM 연결 — 긴 대화가 안 멈추는 이유

AI 가 답을 한 단어씩 만들 때, 앞 단어들의 어텐션 계산은 늘 같다.

그걸 KV 캐시에 보관해 두면, 새 단어 하나만 계산하면 된다.

이 책갈피가 없으면 긴 대화는 기하급수적으로 느려진다. 대신 GPU 메모리를 꽤 차지한다.

더 깊이 — Jay Alammar: Illustrated Transformer

4. 셋을 한 줄에 모아 보기

이제 세 가지가 한 장면에서 어떻게 맞물리는지 익혀 보자.

완성예 — 끝까지 채워진 분석

AI 가 긴 글에 답하는 이 장면을 뜯어보자. 먼저 다 채워진 풀이를 눈으로 익히자.

# 1) 단어를 ID로 바꾼다     → 해시테이블 (O(1))
# 2) 모든 단어가 모두를 본다  → 어텐션 (O(N²))  ← 여기가 폭증 지점
# 3) 앞 계산을 보관해 둔다    → KV 캐시 (O(N²)를 O(N)으로)

가장 무거운 지점 = 어텐션의 O(N²), 그걸 KV 캐시로 누그러뜨린다.

부분완성 — 빈칸을 채워보세요

이번엔 절반만 채워진 분석이다. 아래 상황의 빈칸을 채워 보자.

# 단어 100개에서 같은 단어를 셀 때
# - 리스트에서 매번 통째로 뒤지면     → O(____)
# - 딕셔너리(해시)에 곧장 더하면      → O(____)
# 힌트: 통째로 뒤지면 데이터만큼, 곧장이면 한 번.

(스스로 한번 적어 본 뒤 아래 정답과 맞춰 보자.)

부분완성 정답 비교

위 빈칸의 답은 이렇다.

# - 리스트에서 매번 통째로 뒤지면 → O(N)   (한 명씩 전화)
# - 딕셔너리(해시)에 곧장 더하면   → O(1)   (번호로 즉시)

한 번 훑으며 해시로 더하면 전체가 O(N)으로 끝난다.

독립 적용 — 직접 구분해보세요 (연습)

이번엔 빈칸도 힌트도 없다. 아래 상황이 왜 느린지, 어떤 그릇/기법으로 고칠지 직접 구분해 보자.

# 챗봇이 대화가 길어질수록 한 마디 답하는 시간이 점점 늘어난다.
# 매 답마다 지금까지의 모든 단어 어텐션을 처음부터 다시 계산하고 있다.

질문 — 왜 느려지고, 무엇으로 고칠까?

구분 기준 한 줄 — "이미 한 계산을 또 하고 있으면 보관해서 재사용한다."

답 — 어텐션이 O(N²)라 길어질수록 폭증하는데, 매번 앞 계산을 다시 해서다. KV 캐시로 앞 단어 결과를 보관해 새 단어만 계산하면 O(N)에 가까워진다.

여기서 단순 규칙 하나만 챙기자.

데이터가 늘 때 일이 N²로 불어나는 곳을 찾아, 그릇(해시)이나 책갈피(캐시)로 N에 가깝게 낮춘다.

AI 가 긴 글에서 느려지는 거의 모든 일이 이 N² 때문이고, 그걸 줄이는 게 속도의 핵심이다. 지금은 이 규칙만 들고 가면 된다.

핵심 정리

기억할 세 줄.

데이터가 늘 때 일이 N번 느는지 N²번 느는지부터 읽는다(Big-O).

통째로 뒤지지 말고 번호로 곧장 꺼낸다(해시테이블).

같은 계산을 두 번 하지 말고 보관해 꺼낸다(KV 캐시).

한 문장으로, 어텐션은 모두가 모두를 보는 O(N²)라 느리고, 그걸 KV 캐시로 누그러뜨리는 것이 AI 속도의 핵심이다.

한 걸음 더 ▸ (지금 몰라도 됨)

지금은 "N²를 찾아 그릇·책갈피로 N에 가깝게 낮춘다" 규칙 하나면 충분하다.

다만 "무조건 캐시를 많이 쌓으면 빠르다"가 정답은 아니다.

캐시는 GPU 메모리를 차지해서, 너무 많이 쌓으면 메모리가 모자라기도 한다. 속도와 메모리 사이에 줄다리기가 있다.

어디까지 캐시하고 어디서 멈출지 — 이건 더 깊은 주제라, 지금은 규칙 하나만 들고 가면 된다.

다음 장 예고

다음 장에서는 이렇게 다룬 숫자·그릇 위에서, 단어를 어떻게 숫자 ID 로 잘게 쪼개 다루는지를 본다. 지금은 이 장의 "N²를 그릇·책갈피로 낮춘다" 한 줄만 머리에 있으면 충분하다.